GATE CSE 2008
Q1.
Which of the following is/are true of the auto-increment Addressing Modes? I. It is useful in creating self-relocating code II. If it is included in an Instruction Set Architecture, then an additional ALU is required for effective address calculation III. The amount of increment depends on the size of the data item accessedQ2.
Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous. 1. f(int Y[10], int x) { 2. int i, j, k; 3. i = 0; j = 9; 4. do { 5. k = (i + j) /2; 6. if( Y[k] < x) i = k; else j = k; 7. } while(Y[k] != x && i < j); 8. if(Y[k] == x) printf ("x is in the array ") ; 9. else printf (" x is not in the array ") ; 10. } On which of the following contents of Y and x does the program fail?Q3.
Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous. 1. f(int Y[10], int x) { 2. int i, j, k; 3. i = 0; j = 9; 4. do { 5. k = (i + j) /2; 6. if( Y[k] < x) i = k; else j = k; 7. } while(Y[k] != x && i < j); 8. if(Y[k] == x) printf ("x is in the array ") ; 9. else printf (" x is not in the array ") ; 10. } The correction needed in the program to make it work properly isQ4.
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers isQ5.
You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,...,n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?Q6.
A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?Q7.
Consider the following C functions: int f1(int n) { if(n == 0 || n == 1) return n; else return (2*f1(n-1) + 3*f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N] ; X[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1] = 3; for(i = 2; i <= n; i++) { X[i] = Y[i-1] + Z[i-2]; Y[i] = 2*X[i]; Z[i] = 3*X[i]; } return X[n] ; } The running time of f1(n) and f2(n) areQ8.
Consider the following functions: f(n)=2^{n} g(n)=n! h(n)=n^{log n} Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?Q9.
A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve 3x^{4}-16x^{3}+24x^{2}+37 isQ10.
Let x be a random variable following normal distribution with mean +1 and variance 4. Let Y be another normal variable with mean -1 and variance unknown. If P (x \leq -1) = P (Y \geq2) , the standard deviation of Y is